package basic.study.wantOffer.chapter2;



import basic.study.wantOffer.Public.Node;

import java.util.Stack;

/**
 * @author Kevin
 * @date 2020/4/27 18:30
 */
public class Problem6 {

    private static Node reverse(Node head) {
        if (head.getNext() == null) {
            return head;
        }
        //这里是原先的尾结点，现在的头节点
        Node reversedHead = reverse(head.getNext());
        //原先的头节点，现在的尾节点；和倒数第二个节点相接
        head.getNext().setNext(head);
        head.setNext(null);
        return reversedHead;
    }

    private static Node reverse2(Node head) {
        Node pre = head;
        Node cur = head.getNext();
        Node temp;
        while (cur != null) {
            temp = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = temp;
        }
        head.setNext(null);
        return pre;
    }

    //方法3：不修改链表的情况下，借助栈反转
    public static void reverse3(Node head) {
        Node node = head;
        Stack<String> stack = new Stack<String>();
        while (head.getNext() != null) {
            stack.push(head.getNext().getData());
            head = head.getNext();
        }
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
}
